// 给定一个二叉树，判断它是否是高度平衡的二叉树。

// 本题中，一棵高度平衡二叉树定义为：

//     一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。



// 自顶向下，会重复遍历计算深度。
int depth(struct TreeNode *root) {
    if (root == NULL) return 0;
    return (fmax(depth(root->left), depth(root->right)) + 1);
}

bool isBalanced(struct TreeNode* root){
    if (root == NULL) return true;
    // printf("left: %d    right : %d\n", depth(root->left), depth(root->right));

    return abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}


// 自底向上，边计算深度，边判断
int dfs(struct TreeNode* root) {
    if (root == NULL) return 0;

    int left = dfs(root->left);
    if (left == -1) return -1;
    int right = dfs(root->right);
    if (right == -1) return -1;

    // 符合要求则计算长度，不符合则返回-1
    return (abs(left - right) <= 1)?  (fmax(left, right)+1):-1;
}

bool isBalanced(struct TreeNode* root){
    return dfs(root) != -1;
}